package com.tgy.algorithm.base._二叉树;


class BiTreePNode {
    int value;
    BiTreePNode left;
    BiTreePNode right;
    BiTreePNode parent;
    BiTreePNode(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return this.value + "";
    }
}

public class _二叉树查找后续节点 {

    public static BiTreePNode generalBiTreePNode() {

        /**
         *         1
         *       2   3
         *     4  5 6
         */
        BiTreePNode root = new BiTreePNode(1);
        root.left = new BiTreePNode(2);
        root.left.parent = root;
        root.right = new BiTreePNode(3);
        root.right.parent = root;
        root.left.left = new BiTreePNode(4);
        root.left.left.parent = root.left;
        root.left.right = new BiTreePNode(5);
        root.left.right.parent = root.left;
        root.right.right = new BiTreePNode(6);
        root.right.right.parent = root.right;
        return root;
    }

    public static BiTreePNode findNextNode(BiTreePNode node) {

        if (node.right != null) {
            BiTreePNode nextNode = node.right;
            while (nextNode.left != null) {
                nextNode = nextNode.left;
            }
            return nextNode;
        }

        BiTreePNode nextNode = node.parent;
        while (nextNode != null && nextNode.right == node) {
            node = nextNode;
            nextNode = nextNode.parent;
        }

        return nextNode;
    }

    public static void main(String[] args) {
        BiTreePNode root = generalBiTreePNode();
        BiTreePNode nextNode = findNextNode(root.left.left);
        System.out.println(nextNode);
    }
}
